package a00_LeetCode.LinkedList;

/**
 * @Author quan
 * @Description 返回环形链表的入口节点
 * @Date 2023/3/25 20:04
 */
public class Num142_DetectCycle {
    /**
     * 这个结论我也没理解，是推导出来的，先记着吧！
     * 结论：当快慢指针相遇的时候，引入一个新的节点从链表的头结点开始，最终这个新的节点一定会与慢指针在入口位置相遇
     */
    public ListNode detectCycle(ListNode head) {
        //定义两个快慢指针
        ListNode low = head;
        ListNode fast = head;
        //在快指针没走完的时候
        while (fast!=null && fast.next != null){
            fast = fast.next.next;
            low = low.next;
            if(low == fast){//快慢指针相遇
                ListNode newNode = head;//引入一个新节点
                while (newNode != low){//当慢指针与新节点不相等的时候，让两者一直走
                    low = low.next;
                    newNode = newNode.next;
                }
                //说明慢指针与新节点相遇，此时相遇的位置就是入口
                return newNode;
            }
        }
        return null;
    }
}
